Open Shortest Path First (OSPF) is a routing protocol developed for Internet Protocol (IP) networks. OSPF is a link-state routing protocol that calls for the sending of link-state advertisements (LSAs) to all other routers within the same hierarchical area. Information on attached interfaces, metrics used, and other variables, is included in OSPF LSAs. As OSPF routers accumulate link-state information, they use algorithms that calculate the shortest path to various routers (network nodes). A topological database is essentially an overall picture of networks in relationship to routers. The topological database contains the collection of LSAs received from all routers in the same area. Because routers within the same area share the same information, they have identical topological databases.
The Shortest Path First (SPF) routing algorithm is the basis for OSPF operations. When a router using the SPF algorithm is powered up, it initializes its routing-protocol data structures and then waits for indications from lower-layer protocols that its interfaces are functional. After a router is assured that its interfaces are functioning, it uses the OSPF Hello protocol to acquire neighbors, which are routers with interfaces to a common link. The router sends hello packets to its neighbors and receives their hello packets. In addition to helping acquire neighbors, hello packets also act as “keepalives,” messages that let routers know that other routers are still functional. On multi-access networks (networks supporting more than two routers), the Hello protocol elects a designated router and a backup designated router. Among other things, the designated router is responsible for generating LSAs for the entire multi-access network. Designated routers allow a reduction in network traffic and in the size of the topological database.
When the topological databases of two neighboring routers are synchronized, the routers are said to be adjacent. Adjacencies control the distribution of routing-protocol packets, which are sent and received only on adjacencies. Each router periodically sends its LSAs to provide information on a router's adjacencies or to inform others when a router's state changes. By comparing established adjacencies to link states, failed routers can be detected quickly, and the network's topology can be altered appropriately. From the topological database generated from LSAs, each router calculates a shortest-path tree (SPT), with itself as root. The SPT, in turn, yields a routing table.
When two OSPF neighboring routers establish an adjacency, they go through a finite state machine (FSM). For each neighbor, the router maintains a separate, independent from the other neighbors, FSM. Each FSM goes through several states before establishing adjacency. The two normal long-term states are known to those skilled in the art as “2-way” and “Full.” Depending on the role a router (and its neighbors) play on a particular network, it is expected that the router reach either 2-way or Full state with its neighbors. However, it should never maintain any other state with a neighbor for a prolonged period of time.
In OSPF, before two routers can announce an adjacency to each other and use their common link for forwarding data, they have to exchange their databases through database description (DD) packets to assure that their databases are synchronized. In situations where routers already have a synchronized database and establish a new adjacency over a link, they spend some time in exchanging their database even though their database might be already synchronized. This is a time-consuming process that also requires processing resources on two separate routers.
A hub and spoke topology is defined as a point-to-multipoint network topology where one or more routers, referred to herein as hub routers, are connected to sets of remote routers, referred to herein as spoke routers. In such a topology, a change in one of the spokes is propagated to all of the other spokes although this information is not necessary as the spoke's next hop remains unchanged with respect to the hub. This unnecessary flooding limits the scalability of hub and spoke design. Many enterprise networks have a hub and spoke topology requiring a large deployment of hub and spoke. For example, in a topology having 1000 spoke routers where a hub router typically has 10,000 link state advertisements (LSAs) in its database, it is necessary to make sure that all of those LSA are sent to all of the spoke routers. This consumes substantial CPU time and memory resources, and beyond a certain level either the CPUs are running high (often at 100% of their capacity) or the memory completely consumed, thus limiting the number of LSAs and spokes that can be accommodated in the topology.